package _interview150;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 57. 插入区间
 */
public class No57 {
    public int[][] insert(int[][] oldIntervals, int[] newInterval) {
        int n = oldIntervals.length + 1;
        int[][] intervals = new int[n][2];
        intervals[0] = newInterval;
        System.arraycopy(oldIntervals, 0, intervals, 1, n - 1);
        Arrays.sort(intervals, ((o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]));
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(intervals[0]);
        for (int i = 1; i < n; i++) {
            while (i < n && queue.peekLast()[1] >= intervals[i][0]) {
                queue.peekLast()[1] = Math.max(intervals[i][1], queue.peekLast()[1]);
                i++;
            }
            if (i < n) queue.offer(intervals[i]);
        }
        int[][] ans = new int[queue.size()][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = queue.poll();
        }
        return ans;
    }
}
